#include <memory>
#include <iostream>

using DataType = int;

class Node;

using NodePtr = std::shared_ptr<Node>;
using WeakRef = std::weak_ptr<Node>;

enum class Color : int
{
    RED = 0,
    BLACK = 1,
    DOUBLEBLACK = 2
};

enum class Order
{
    Preorder = 0,
    Inorder,
    Postorder
};

class Node
{
public:
    Node()
        : data_(nullptr), color_{Color::BLACK}
    {
    }
    Node(const DataType& data, NodePtr left, NodePtr right, NodePtr parent)
        : left_(left), right_(right), parent_(parent)
        , data_(new DataType(data))
    {
    }
    Node(DataType&& data, NodePtr left, NodePtr right, NodePtr parent)
        : left_(left), right_(right), parent_(parent)
        , data_(new DataType(std::move(data)))
    {
    }

    const DataType& value() const
    {
        return *data_;
    }

    void setValue(const DataType& data)
    {
        data_.reset(new DataType(data));
    }

    void swapValue(NodePtr& that)
    {
        data_.swap(that->data_);
    }

    bool hasLeftChild() const
    {
        return left_ != nullptr;
    }

    bool hasRightChild() const
    {
        return right_ != nullptr;
    }

    bool hasRedColorChild() const
    {
        return (left_->color_ == Color::RED) || (right_->color_ == Color::RED);
    }

    Color color() const
    {
        return color_;
    }

    void setColor(Color c)
    {
        color_ = c;
    }

    void add()
    {
        color_ == Color::RED ?
            color_ = Color::BLACK :
            color_ == Color::BLACK ?
                color_ = Color::DOUBLEBLACK :
                color_ = Color::DOUBLEBLACK;
    }

    void sub()
    {
        color_ == Color::DOUBLEBLACK ?
            color_ = Color::BLACK :
            color_ == Color::BLACK ?
            color_ = Color::RED :
            color_ = Color::RED;
    }

    bool operator==(const Node& other) const
    {
        return value() == other.value();
    }

    bool operator<(const Node& other) const
    {
        return value() < other.value();
    }

    bool operator>(const Node& other) const
    {
        return value() > other.value();
    }

    NodePtr left_;
    NodePtr right_;
    WeakRef parent_;
private:

    std::unique_ptr<DataType> data_;
    Color color_ {Color::RED};
};

class RBTree
{
public:
    RBTree()
        : null_(new Node()), root_(null_)
    {
    }

    void insert(DataType data)
    {
        root_ = insert(root_, data);
        root_->setColor(Color::BLACK);
    }

    void erase(DataType data)
    {
        root_ = erase(root_, data);
        root_->setColor(Color::BLACK);
    }

    void print(Order o)
    {
        switch (o)
        {
            case Order::Preorder:
                preorder(root_); break;
            case Order::Inorder:
                inorder(root_); break;
            case Order::Postorder:
                postorder(root_); break;
        }
        std::cout << std::endl;
    }

    void print()
    {
        std::cout << "Preorder: ";
        preorder(root_);
        std::cout << std::endl;
        std::cout << "Inorder: ";
        inorder(root_);
        std::cout << std::endl;
        std::cout << "Postorder: ";
        postorder(root_);
        std::cout << std::endl;
    }

private:

    NodePtr insert(NodePtr root, const DataType& data)
    {
        if (root == null_)
            return std::shared_ptr<Node>(new Node(data, null_, null_, root));
        if (root->value() == data)
            return root;
        if (root->value() < data)
            root->right_ = insert(root->right_, data);
        else
            root->left_ = insert(root->left_, data);

        return insertAdjustment(root);
    }

    NodePtr erase(NodePtr root, const DataType& data)
    {
        if (root == null_)
            return null_;
        if (root->value() < data)
        {
            root->right_ = erase(root->right_, data);
        }
        else if (root->value() > data)
        {
            root->left_ = erase(root->left_, data);
        }
        else
        {
            if (root->left_ == null_ || root->right_ == null_)
            {
                auto temp = root->left_ != null_ ? root->left_ : root->right_;
                if (root->color() != Color::RED)
                    temp->add();
                return temp;
            }
            auto temp = pred(root);
            root->setValue(temp->value());
            root->left_ = erase(root->left_, temp->value());
        }

        return eraseAdjustment(root);
    }

    NodePtr leftRotate(NodePtr root)
    {
        auto temp = root->right_;
        root->right_ = temp->left_;
        temp->left_ = root;
        return temp;
    }

    NodePtr rightRotate(NodePtr root)
    {
        auto temp = root->left_;
        root->left_ = temp->right_;
        temp->right_ = root;
        return temp;
    }

    NodePtr insertAdjustment(NodePtr root)
    {
        if (!root->hasRedColorChild())
            return root;
        do {
            int flag = 0;
            if (root->left_->color() == Color::RED
                && root->right_->color() == Color::RED)
                break;
            if (root->left_->color() == Color::RED && root->left_->hasRedColorChild())
                flag = 1;
            if (root->right_->color() == Color::RED && root->right_->hasRedColorChild())
                flag = 2;
            if (flag == 0)
                return root;
            if (flag == 1)
            {
                if (root->left_->right_->color() == Color::RED)
                    root->left_ = leftRotate(root->left_);
                root = rightRotate(root);
            }
            else
            {
                if (root->right_->left_->color() == Color::RED)
                    root->right_ = rightRotate(root->right_);
                root = leftRotate(root);
            }
            break;
        } while (1);
        root->setColor(Color::RED);
        root->left_->setColor(Color::BLACK);
        root->right_->setColor(Color::BLACK);
        return root;
    }

    NodePtr eraseAdjustment(NodePtr root)
    {
        if (root->left_->color() != Color::DOUBLEBLACK
            && root->right_->color() != Color::DOUBLEBLACK)
            return root;
        if (root->hasRedColorChild())
        {
            int flag = 0;
            root->setColor(Color::RED);
            if (root->left_->color() == Color::DOUBLEBLACK && root->right_->color() == Color::RED)
            {
                root = leftRotate(root);
                flag = 1;
            }
            else
            {
                root = rightRotate(root);
            }
            root->setColor(Color::BLACK);
            if (flag)
            {
                root->left_ = eraseAdjustment(root->left_);
            }
            else
            {
                root->right_ = eraseAdjustment(root->right_);
            }
            return root;
        }

        if (root->left_->color() == Color::DOUBLEBLACK && !root->right_->hasRedColorChild() ||
            (root->right_->color() == Color::DOUBLEBLACK && !root->left_->hasRedColorChild()))
        {
            root->left_->sub();
            root->right_->sub();
            root->add();
            return root;
        }

        if (root->left_->color() == Color::DOUBLEBLACK)
        {
            root->left_->setColor(Color::RED);
            if (root->right_->right_->color() != Color::RED)
            {
                root->right_->setColor(Color::RED);
                root->right_ = rightRotate(root->right_);
                root->right_->setColor(Color::BLACK);
            }
            root = leftRotate(root);
            root->setColor(root->left_->color());
        }
        else
        {
            root->right_->setColor(Color::RED);
            if (root->left_->left_->color() != Color::RED)
            {
                root->left_->setColor(Color::RED);
                root->left_ = leftRotate(root->left_);
                root->left_->setColor(Color::BLACK);
            }
            root = rightRotate(root);
            root->setColor(root->right_->color());
        }
        return root;
    }

    NodePtr pred(NodePtr root)
    {
        auto temp = root->left_;
        while (temp->right_ != null_)
            temp = temp->right_;
        return temp;
    }

    void inorder(NodePtr root)
    {
        if (root == null_)
        {
            return;
        }
        inorder(root->left_);
        prettyPrint(root);
        inorder(root->right_);
    }

    void preorder(NodePtr root)
    {
        if (root == null_)
        {
            return;
        }
        prettyPrint(root);
        preorder(root->left_);
        preorder(root->right_);
    }

    void postorder(NodePtr root)
    {
        if (root == null_)
        {
            return;
        }
        postorder(root->left_);
        postorder(root->right_);
        prettyPrint(root);
    }

    void prettyPrint(NodePtr root)
    {
        const char* fmtstr = nullptr;
        if (root->color() == Color::RED)
            fmtstr = "\033[1;31m#%d#\033[0m";
        else if (root->color() == Color::BLACK && root != null_)
            fmtstr = "\033[1;37m#%d#\033[0m";
        else if (root->color() == Color::DOUBLEBLACK && root != null_)
            fmtstr = "\033[1;34m#%d#\033[0m";

        char buf[32];
        snprintf(buf, sizeof(buf) - 1, fmtstr, root->value());
        std::cout << buf << " ";
    }

private:

    NodePtr null_;
    NodePtr root_;
};